package com.adamjwh.sort;

/**
 * 堆排序
 * 
 * @author adamjwh
 * 
 * 算法描述：
 * 将初始待排序关键字序列(R1,R2….Rn)构建成大顶堆，此堆为初始的无序区；
 * 将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区(R1,R2,……Rn-1)和新的有序区(Rn),且满足R[1,2…n-1]<=R[n]；
 * 由于交换后新的堆顶R[1]可能违反堆的性质，因此需要对当前无序区(R1,R2,……Rn-1)调整为新堆，然后再次将R[1]与无序区最后一个元素交换，得到新的无序区(R1,R2….Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成。
 *
 */
public class HeapSort {

	public static void heapSort(int[] array) {
		
		for(int i=array.length/2-1; i>=0; i--) {	//构建一个大顶堆
			adjustHeap(array, i, array.length-1);
		}
		
		for(int i=array.length-1; i>=0; i--) {	//将堆顶记录和当前未经排序子序列的最后一个记录交换
			int temp = array[0];
			array[0] = array[i];
			array[i] = temp;
			
			adjustHeap(array, 0, i-1);
		}
		
	}

	
	//构造大根堆
	public static void adjustHeap(int[] array, int parent, int length) {
		int temp = array[parent];
		
		for(int child=2*parent; child<length; child*=2) {
			// 如果有右孩子结点，并且右孩子结点的值大于左孩子结点，则选取右孩子结点 
			if(child<length && array[child]<array[child+1]) {
				++child;
			}
			
			// 如果父结点的值已经大于孩子结点的值，则直接结束
			if(temp >= array[child]) {
				break;
			}
			
			array[parent] = array[child];
			parent = child;
		}
		array[parent] = temp;
	}
	
	//测试
	public static void main(String[] args) {
	    int[] arr = {1,9,3,12,7,8,3,4,65,22};

	    heapSort(arr);

	    for(int i:arr){
	        System.out.print(i+",");
	    }
	}
	
}
